//57.插入区间
//https://leetcode.cn/problems/insert-interval
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        int l = newInterval[0],r = newInterval[1];
        vector<vector<int>> ret;
        ret.reserve(n);
        int i = 0;
        for(;i<n;++i)
        {
            if(r < intervals[i][0])
            {
                ret.push_back({ l, r });
                l = -1;
                r = -1;
                break;
            }
            else if(l > intervals[i][1]) ret.emplace_back(intervals[i]);
            else //合并区间
            {
                l = min(l,intervals[i][0]);
                r = max(r,intervals[i][1]);
            }
        }

        while(i < n) ret.emplace_back(intervals[i++]);
        if(l != -1 && r != -1) ret.push_back({ l, r });
        return ret;
    }
};